#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define inf 100000001

struct comp {
	string type, name;
	int price, quality;
};

int ntest, l, r, n, result;
long long sum, b, startSum;
vector<comp> c;

bool cmp(comp a, comp b ) {
  return a.quality < b.quality;
}

map<string, int> m;

int main()
{
	//freopen("A.in", "r", stdin);

	scanf("%d\n", &ntest);

	while (0 < ntest--)
	{
		//input
		scanf("%d %d\n", &n, &b);

		c.clear();
		for (int i = 0; i < n; i++)
		{
			string s;
			getline(cin, s);
			istringstream ss(s);
			comp temp;
			ss >> temp.type >> temp.name >> temp.price >> temp.quality;
			c.push_back(temp);
		}

		result = -1;

		l = 0;
		r = 0;
		for (int k = 0; k < n; k++)
			if (r < c[k].quality) r = c[k].quality;

		//cout << l << " " << r << endl;

		startSum = 0;
		m.clear();
		for (int k = 0; k < n; k++)
			if (m[c[k].type] != inf)
			{
				m[c[k].type] = inf;
				startSum += (long long) inf;
			}
		//cout << "startsum " << startSum << endl;

		while (l <= r)
		{
			int mid = (l+r)/2;
			//cout << mid << endl;

			sum = startSum;
			for (int i = 0; i < n; i++)
				if (m[c[i].type] != inf) m[c[i].type] = inf;

			for (int i = 0; i < n; i++)
				if (c[i].quality >= mid)
					if (m[c[i].type] > c[i].price)
					{
						//cout << c[i].type << " " << c[i].name << " " << c[i].price << " " << c[i].type << endl;
						sum -= (long long) m[c[i].type];
						m[c[i].type] = c[i].price;
						sum += (long long) c[i].price;
						//cout << "sum " << sum << endl;
					}

			if (sum <= b)
			{
				l = mid+1;
				result = mid;
			}
			else r = mid-1;
		}

		cout << result << endl;
	}
	return 0;
}
